[01背包] 背包问题求方案数(01背包+求方案数+求最优解方案数+思维)

2023-10-18 03:54| 来源: 网络整理| 查看: 265

文章目录 0. 前言1. 01背包+求方案数+思维

0. 前言

相关：

[背包] 背包问题算法模板(模板)

强相关：

[01背包] 背包问题求具体方案(01背包+求方案数+思维) 1. 01背包+求方案数+思维

11. 背包问题求方案数

在这里插入图片描述本问题和 [01背包] 背包问题求具体方案(01背包+求方案数+思维) 求方案数不同。上个问题是求一条具体的最短路状态转移方案即可，因为会对字典序排序，所以当时我们采用了贪心的策略，当两个状态相等时，选小不选大。而本问题，这两个状态相等时，就把这两个都选上就行了。

这个问题代表了求最优解的方案数，也是代表了一大类问题，重要。而求解具体的一个方案，也是很重要的。并且一般让求方案的题，都不简单！

开辟一个新数组，g[i][j] 记录转移到 f[i][j] 的方案数是多少就行了，针对 f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi)，对应着选 i、不选 i 的两种情况。那么 g[i-1][j] 就是 f[i-1][j] 的方案数。g[i-1][j-vi] 就是 g[i-1][j-vi] 的方案数

当 f[i-1][j] < f[i-1][j-vi]+wi 的时候，g[i][j] = g[i-1][j]当 f[i-1][j] > f[i-1][j-vi]+wi 的时候，g[i][j] = g[i-1][j-vi]当 f[i-1][j] = f[i-1][j-vi]+wi 的时候，g[i][j] = g[i-1][j]+g[i-1][j-vi]

能够发现，f 和 g 都是仅和上一层有关系。所以都可以优化至一维。

在此，表示的是体积恰好是 j 的方案数。如果表示成体积最大是 j 的话计算起来会比较麻烦。因为在 01 背包中我们将体积定义为最大，实际上对于 f[m] 可能其并没有用到，但是仍旧能够转移过来。那么这个方案数就不好进行累加，因为相等的部分很多，得将这些无效转移剔除，所以比较麻烦。但是在此将状态转移与最大值精确对应起来，找到

代码：

#include #include #include using namespace std; const int N = 1005; const int MOD = 1e9+7; int n, m; int f[N]; // f[j]是容积“恰好”为j时的最优解 int g[N]; // g[j]是容积“恰好”为j时的最优解的方案数 int main() { cin >> n >> m; // 背包容量为0时，这些状态都不合法，此时状态的第二维表示的不是最多而是恰好 // 那么如果一件物品都没有，第二维的体积必须是0。 memset(f, -0x3f, sizeof f); f[0] = 1; g[0] = 1; for (int i = 0; i int maxv = max(f[j], f[j - v] + w); int cnt = 0; if (maxv == f[j]) cnt += g[j]; if (maxv == f[j - v] + w) cnt += g[j - v]; g[j] = cnt % MOD; // 是f[j]等于maxv这个容积下的最优解方案数 f[j] = maxv; // 那么在不同容积下到达同样的最大值，最优解方案不同且需要累加 } } // 最终不一定占满全部背包体积，01背包在此仍会转移到f[m] // 而在此由于方案数g[j]和f[j]严格对应,所以必须找到准确的取到最优解时的体积 int res = 0; // 这里状态定义是恰好,所有需要遍历求解最大值 for (int i = 0; i int left = f[j], right = f[j - v[i]] + w[i]; f[j] = max(left, right); if (left > right) g[j] = g[j]; else if (left

【本文地址】

公司简介

联系我们